Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
- Only numbers
1through9are used. - Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
Example 1:
Input: k = 3, n = 7 Output: [[1,2,4]] Explanation: 1 + 2 + 4 = 7 There are no other valid combinations.
Example 2:
Input: k = 3, n = 9 Output: [[1,2,6],[1,3,5],[2,3,4]] Explanation: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 There are no other valid combinations.
Example 3:
Input: k = 4, n = 1 Output: [] Explanation: There are no valid combinations. Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.
Example 4:
Input: k = 3, n = 2 Output: [] Explanation: There are no valid combinations.
Example 5:
Input: k = 9, n = 45 Output: [[1,2,3,4,5,6,7,8,9]] Explanation: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45 There are no other valid combinations.
Constraints:
2 <= k <= 91 <= n <= 60
Average Rating: 4.87 (31 votes)
Solution
Approach 1: Backtracking
Intuition
The problem asks us to come up with some fixed-length combinations that meet certain conditions.
To solve the problem, it would be beneficial to build a combination by hand.
If we represent the combination as an array, we then could fill the array one element at a time.
For example, given the input k=3 and n=9, i.e. the size of the combination is 3, and the sum of the digits in the combination should be 9. Here are a few steps that we could do:
- 1). We could pick a digit for the first element in the combination.
Initially, the list of candidates is
[1, 2, 3, 4, 5, 6, 7, 8. 9]for any element in the combination, as stated in the problem. Let us pick1as the first element. The current combination is[1].
-
2). Now that we picked the first element, we have two more elements to fill in the final combination. Before we proceed, let us review the conditions that we should fullfil for the next steps.
-
Since we've already picked the digit
1, we should exclude the digit from the original candidate list for the remaining elements, in order to ensure that the combination does not contain any duplicate digits, as required in the problem. -
In addition, the sum of the remaining two elements should be 9−1=8.
-
-
3). Based on the above conditions, for the second element, we could have several choices. Let us pick the digit
2, which is not a duplicate of the first element, plus it does not exceed the desired sum (i.e. 8) neither. The combination now becomes[1, 2].
- 4). Now for the third element, with all the constraints, it leaves us no choice but to pick the digit
6as the final element in the combination of[1, 2, 6].
-
5). As we mentioned before, for the second element, we could have several choices. For instance, we could have picked the digit
3, instead of the digit2. Eventually, it could lead us to another solution as[1, 3, 5]. -
6). As one can see, for each element in the combination, we could revisit our choices, and try out other possibilities to see if it leads to a valid solution.
If you have followed the above steps, it should become evident that backtracking would be the technique that we could use to come up an algorithm for this problem.
Indeed, we could resort to backtracking, where we try to fill the combination one element at a step. Each choice we make at certain step might lead us to a final solution. If not, we simply revisit the choice and try out other choices, i.e. backtrack.
Algorithm
There are many ways to implement a backtracking algorithm. One could also refer to our Explore card where we give some examples of backtracking algorithms.
To implement the algorithm, one could literally follow the steps in the Intuition section. However, we would like to highlight a key trick that we employed, in order to ensure the non-redundancy among the digits within a single combination, as well as the non-redundancy among the combinations.
The trick is that we pick the candidates in order. We treat the candidate digits as a list with order, i.e.
[1, 2, 3, 4, 5, 6, 7, 8. 9]. At any given step, once we pick a digit, e.g.6, we will not consider any digits before the chosen digit for the following steps, e.g. the candidates are reduced down to[7, 8, 9].
With the above strategy, we could ensure that a digit will never be picked twice for the same combination. Also, all the combinations that we come up with would be unique.
Here are some sample implementations based on the above ideas.
Complexity Analysis
Let K be the number of digits in a combination.
-
Time Complexity: O((9−K)!9!⋅K)
-
In a worst scenario, we have to explore all potential combinations to the very end, i.e. the sum n is a large number (n>9∗9). At the first step, we have 9 choices, while at the second step, we have 8 choices, so on and so forth.
-
The number of exploration we need to make in the worst case would be P(9,K)=(9−K)!9!, assuming that K<=9. By the way, K cannot be greater than 9, otherwise we cannot have a combination whose digits are all unique.
-
Each exploration takes a constant time to process, except the last step where it takes O(K) time to make a copy of combination.
-
To sum up, the overall time complexity of the algorithm would be (9−K)!9!⋅O(K)=O((9−K)!9!⋅K).
-
-
Space Complexity: O(K)
-
During the backtracking, we used a list to keep the current combination, which holds up to K elements, i.e. O(K).
-
Since we employed recursion in the backtracking, we would need some additional space for the function call stack, which could pile up to K consecutive invocations, i.e. O(K).
-
Hence, to sum up, the overall space complexity would be O(K).
-
Note that, we did not take into account the space for the final results in the space complexity.
-
November 20, 2020 11:35 AM
This is a question whose big O problem is more difficult and complex than the question itself...
Last Edit: September 12, 2020 1:59 PM
I think this problem involves combination. In terms of combination, the time complexity is O(C(9,k)) = O(9!/(k! * (9-k)!). There is no duplicate in each combination, and the order of numbers doesn't matter. It can be faster since all numbers sum up to n, and the case numbers added up more than n can return earlier.
Last Edit: September 6, 2020 8:24 PM
I am confused by the time complexity analysis:
At the first step, we have 9 choices, while at the second step, we have 8 choices, so on and so forth.
It is true that we have 9 choices at the first step, but the number of choices in the second step depends on our choice in first step. If we choose 1 in step1, then we have 8 choices in step2, if we choose 6 in step1, we only have 3 choices in step2. So not all step2 has same 8 choices. And this applies to all remaining steps.
Saying that the time complexity is O(9!/(9 - K)!) is right though, but is this upper bound too high? Is this like saying O(n^2) is the upper bound of a linear algorithm? it is definitely true, but we can have more precise upper bound O(n).
On the other hand, this could be the O(1 + 2 + ... + n) = O(n^2) case. Can anyone help me?
PS: I tried k = [0:9], n = 45 (I think as long as n >= 45, it will exhaust all searches until comb.size() == k), and counted the number of times backtrack() was invoked (this includes every recursive call in the for loop). I compared the growth rate of this number with 9!/(9 - K)!:
| k | backtrack() invoked |
9!/(9 - k)! |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 10 | 9 |
| 2 | 46 | 72 |
| 3 | 130 | 504 |
| 4 | 256 | 3024 |
| 5 | 382 | 15120 |
| 6 | 466 | 60480 |
| 7 | 502 | 181440 |
| 8 | 511 | 362880 |
| 9 | 512 | 362880 |
September 13, 2020 12:56 AM
The number of steps should actually be bounded by a constant because if n > 45 the result is always an empty list. If the algorithm returns [] whenever n > 45, the time complexity would be O(1).
December 27, 2020 9:00 AM
time complexity of O(C(9,k)) makes intuitive sense. I don't know how to derive the time complexity above.
Last Edit: September 15, 2020 2:42 PM
Wouldn't the time complexity be simply ~O(9Ck) rather than ~O(9Ck * k)? My reasoning was that, although it takes ~O(k) time to deeply copy the combination, not every branch in the recursion tree will need to copy the combination. In fact, it seemed to me that only a very small number of branch would end up copying the combination, as most branch will end up not arriving at the answer. But technically ~O(9Ck * k) is a correct loose upperbound.
Could anyone explain how to correctly reason about the time complexity?
September 14, 2020 6:11 AM
In the python version, line 7 -- why is it necessary to append(list(comb)) rather than just append(comb) ?
I tried it without wrapping comb and see that the result is appending an empty list to results but does anyone know why this is? Both type(comb) and type(list(comb)) return <class 'list'> and also the output of print(comb) and print(list(comb)) appear identical. print(comb == list(comb)) likewise results in True.
And yet results.append(comb) results in appending empty lists while results.append(list(comb)) actually does append the list as expected.
October 7, 2020 6:23 AM
Can you explain how does the trick guarantee each subset generated this way is unique?
Last Edit: September 12, 2020 7:48 PM
Can anyone tell me why are we removing the last element on line 19?
Is it that in backtracking we have to remove ONLY the last element?
September 12, 2020 7:14 PM
I don't know how should I estimate the time complexity of my solution below:
vector<vector<int>> combinationSum3(int k, int n) {
if (!k || k > 9) return {};
const vector<vector<int>> REF{{0, 1, 3, 6, 10, 15, 21, 28, 36, 45},
{0, 9,17,24, 30, 35, 39, 42, 44, 45}};
vector<vector<int>> ans;
vector<int> buf(k, 0);
for (int i = 0, sum = 0; i >= 0; ) {
if (i == k - 1) {
int r = n - sum;
if (r > (i ? buf[i-1] : 0) && r < 10) {
buf[i] = r;
ans.push_back(buf);
}
--i;
continue;
}
sum -= buf[i]++;
int p = (i ? buf[i-1] : 0), r = n - sum, rc = k - i;
if (buf[i] <= p) buf[i] = p + 1;
if (buf[i] > 9 || p + rc > 9 || r < REF[0][p+rc] - REF[0][p] || r > REF[1][rc]) {
buf[i--] = 0;
continue;
}
sum += buf[i++];
}
return ans;
}
I tried to trim all the impossible branches as early as possible.
Then I counted how much "efforts" (number of loops) is needed for any k/n input:
(Since 45 is the largest sum from 1 to 9, for n > 45 the effort is always "1")
k1,n1: 1 | k1,n2: 1 | k1,n3: 1 | k1,n4: 1 | k1,n5: 1 |
k1,n6: 1 | k1,n7: 1 | k1,n8: 1 | k1,n9: 1 | k1,n10: 1 |
k1,n11: 1 | k1,n12: 1 | k1,n13: 1 | k1,n14: 1 | k1,n15: 1 |
k1,n16: 1 | k1,n17: 1 | k1,n18: 1 | k1,n19: 1 | k1,n20: 1 |
k1,n21: 1 | k1,n22: 1 | k1,n23: 1 | k1,n24: 1 | k1,n25: 1 |
k1,n26: 1 | k1,n27: 1 | k1,n28: 1 | k1,n29: 1 | k1,n30: 1 |
k1,n31: 1 | k1,n32: 1 | k1,n33: 1 | k1,n34: 1 | k1,n35: 1 |
k1,n36: 1 | k1,n37: 1 | k1,n38: 1 | k1,n39: 1 | k1,n40: 1 |
k1,n41: 1 | k1,n42: 1 | k1,n43: 1 | k1,n44: 1 | k1,n45: 1 |
k2,n1: 1 | k2,n2: 1 | k2,n3: 19 | k2,n4: 19 | k2,n5: 19 |
k2,n6: 19 | k2,n7: 19 | k2,n8: 19 | k2,n9: 19 | k2,n10: 19 |
k2,n11: 19 | k2,n12: 19 | k2,n13: 19 | k2,n14: 19 | k2,n15: 19 |
k2,n16: 19 | k2,n17: 19 | k2,n18: 1 | k2,n19: 1 | k2,n20: 1 |
k2,n21: 1 | k2,n22: 1 | k2,n23: 1 | k2,n24: 1 | k2,n25: 1 |
k2,n26: 1 | k2,n27: 1 | k2,n28: 1 | k2,n29: 1 | k2,n30: 1 |
k2,n31: 1 | k2,n32: 1 | k2,n33: 1 | k2,n34: 1 | k2,n35: 1 |
k2,n36: 1 | k2,n37: 1 | k2,n38: 1 | k2,n39: 1 | k2,n40: 1 |
k2,n41: 1 | k2,n42: 1 | k2,n43: 1 | k2,n44: 1 | k2,n45: 1 |
k3,n1: 1 | k3,n2: 1 | k3,n3: 1 | k3,n4: 1 | k3,n5: 1 |
k3,n6: 35 | k3,n7: 35 | k3,n8: 35 | k3,n9: 49 | k3,n10: 49 |
k3,n11: 49 | k3,n12: 61 | k3,n13: 61 | k3,n14: 61 | k3,n15: 71 |
k3,n16: 71 | k3,n17: 71 | k3,n18: 79 | k3,n19: 63 | k3,n20: 49 |
k3,n21: 43 | k3,n22: 33 | k3,n23: 25 | k3,n24: 23 | k3,n25: 1 |
k3,n26: 1 | k3,n27: 1 | k3,n28: 1 | k3,n29: 1 | k3,n30: 1 |
k3,n31: 1 | k3,n32: 1 | k3,n33: 1 | k3,n34: 1 | k3,n35: 1 |
k3,n36: 1 | k3,n37: 1 | k3,n38: 1 | k3,n39: 1 | k3,n40: 1 |
k3,n41: 1 | k3,n42: 1 | k3,n43: 1 | k3,n44: 1 | k3,n45: 1 |
k4,n1: 1 | k4,n2: 1 | k4,n3: 1 | k4,n4: 1 | k4,n5: 1 |
k4,n6: 1 | k4,n7: 1 | k4,n8: 1 | k4,n9: 1 | k4,n10: 49 |
k4,n11: 49 | k4,n12: 49 | k4,n13: 61 | k4,n14: 87 | k4,n15: 87 |
k4,n16: 97 | k4,n17: 107 | k4,n18: 129 | k4,n19: 137 | k4,n20: 145 |
k4,n21: 139 | k4,n22: 151 | k4,n23: 135 | k4,n24: 123 | k4,n25: 109 |
k4,n26: 93 | k4,n27: 65 | k4,n28: 47 | k4,n29: 31 | k4,n30: 29 |
k4,n31: 1 | k4,n32: 1 | k4,n33: 1 | k4,n34: 1 | k4,n35: 1 |
k4,n36: 1 | k4,n37: 1 | k4,n38: 1 | k4,n39: 1 | k4,n40: 1 |
k4,n41: 1 | k4,n42: 1 | k4,n43: 1 | k4,n44: 1 | k4,n45: 1 |
k5,n1: 1 | k5,n2: 1 | k5,n3: 1 | k5,n4: 1 | k5,n5: 1 |
k5,n6: 1 | k5,n7: 1 | k5,n8: 1 | k5,n9: 1 | k5,n10: 1 |
k5,n11: 1 | k5,n12: 1 | k5,n13: 1 | k5,n14: 1 | k5,n15: 61 |
k5,n16: 61 | k5,n17: 61 | k5,n18: 71 | k5,n19: 93 | k5,n20: 129 |
k5,n21: 137 | k5,n22: 145 | k5,n23: 171 | k5,n24: 183 | k5,n25: 209 |
k5,n26: 203 | k5,n27: 203 | k5,n28: 187 | k5,n29: 173 | k5,n30: 155 |
k5,n31: 135 | k5,n32: 91 | k5,n33: 63 | k5,n34: 39 | k5,n35: 37 |
k5,n36: 1 | k5,n37: 1 | k5,n38: 1 | k5,n39: 1 | k5,n40: 1 |
k5,n41: 1 | k5,n42: 1 | k5,n43: 1 | k5,n44: 1 | k5,n45: 1 |
k6,n1: 1 | k6,n2: 1 | k6,n3: 1 | k6,n4: 1 | k6,n5: 1 |
k6,n6: 1 | k6,n7: 1 | k6,n8: 1 | k6,n9: 1 | k6,n10: 1 |
k6,n11: 1 | k6,n12: 1 | k6,n13: 1 | k6,n14: 1 | k6,n15: 1 |
k6,n16: 1 | k6,n17: 1 | k6,n18: 1 | k6,n19: 1 | k6,n20: 1 |
k6,n21: 71 | k6,n22: 71 | k6,n23: 71 | k6,n24: 79 | k6,n25: 97 |
k6,n26: 127 | k6,n27: 177 | k6,n28: 173 | k6,n29: 185 | k6,n30: 195 |
k6,n31: 207 | k6,n32: 205 | k6,n33: 221 | k6,n34: 177 | k6,n35: 149 |
k6,n36: 121 | k6,n37: 83 | k6,n38: 49 | k6,n39: 47 | k6,n40: 1 |
k6,n41: 1 | k6,n42: 1 | k6,n43: 1 | k6,n44: 1 | k6,n45: 1 |
k7,n1: 1 | k7,n2: 1 | k7,n3: 1 | k7,n4: 1 | k7,n5: 1 |
k7,n6: 1 | k7,n7: 1 | k7,n8: 1 | k7,n9: 1 | k7,n10: 1 |
k7,n11: 1 | k7,n12: 1 | k7,n13: 1 | k7,n14: 1 | k7,n15: 1 |
k7,n16: 1 | k7,n17: 1 | k7,n18: 1 | k7,n19: 1 | k7,n20: 1 |
k7,n21: 1 | k7,n22: 1 | k7,n23: 1 | k7,n24: 1 | k7,n25: 1 |
k7,n26: 1 | k7,n27: 1 | k7,n28: 79 | k7,n29: 79 | k7,n30: 79 |
k7,n31: 85 | k7,n32: 99 | k7,n33: 115 | k7,n34: 149 | k7,n35: 183 |
k7,n36: 179 | k7,n37: 153 | k7,n38: 147 | k7,n39: 111 | k7,n40: 107 |
k7,n41: 61 | k7,n42: 59 | k7,n43: 1 | k7,n44: 1 | k7,n45: 1 |
k8,n1: 1 | k8,n2: 1 | k8,n3: 1 | k8,n4: 1 | k8,n5: 1 |
k8,n6: 1 | k8,n7: 1 | k8,n8: 1 | k8,n9: 1 | k8,n10: 1 |
k8,n11: 1 | k8,n12: 1 | k8,n13: 1 | k8,n14: 1 | k8,n15: 1 |
k8,n16: 1 | k8,n17: 1 | k8,n18: 1 | k8,n19: 1 | k8,n20: 1 |
k8,n21: 1 | k8,n22: 1 | k8,n23: 1 | k8,n24: 1 | k8,n25: 1 |
k8,n26: 1 | k8,n27: 1 | k8,n28: 1 | k8,n29: 1 | k8,n30: 1 |
k8,n31: 1 | k8,n32: 1 | k8,n33: 1 | k8,n34: 1 | k8,n35: 1 |
k8,n36: 85 | k8,n37: 85 | k8,n38: 85 | k8,n39: 83 | k8,n40: 81 |
k8,n41: 79 | k8,n42: 77 | k8,n43: 75 | k8,n44: 73 | k8,n45: 1 |
k9,n1: 1 | k9,n2: 1 | k9,n3: 1 | k9,n4: 1 | k9,n5: 1 |
k9,n6: 1 | k9,n7: 1 | k9,n8: 1 | k9,n9: 1 | k9,n10: 1 |
k9,n11: 1 | k9,n12: 1 | k9,n13: 1 | k9,n14: 1 | k9,n15: 1 |
k9,n16: 1 | k9,n17: 1 | k9,n18: 1 | k9,n19: 1 | k9,n20: 1 |
k9,n21: 1 | k9,n22: 1 | k9,n23: 1 | k9,n24: 1 | k9,n25: 1 |
k9,n26: 1 | k9,n27: 1 | k9,n28: 1 | k9,n29: 1 | k9,n30: 1 |
k9,n31: 1 | k9,n32: 1 | k9,n33: 1 | k9,n34: 1 | k9,n35: 1 |
k9,n36: 1 | k9,n37: 1 | k9,n38: 1 | k9,n39: 1 | k9,n40: 1 |
k9,n41: 1 | k9,n42: 1 | k9,n43: 1 | k9,n44: 1 | k9,n45: 89 |
The worst case is 209 for k5/n25 (12 combinations). This is way less than the analysis given by the solution (9!*5/(9-5)! = 75600). And for more than half of the cases it simply returns.
I would say, maybe some times the complexity is just "not esitmatable".
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 09/12/2020 20:02 | Accepted | 4 ms | 6.8 MB | cpp |
xxxxxxxxxxclass Solution {public: vector<vector<int>> combinationSum3(int k, int n) { }};